1⎇⎇␈F1␈F21.␈→1044⎇19⎇1⎇0⎇⎇static structure     16412⎇␈F1␈←
2⎇⎇␈F1␈→1136⎇0⎇2⎇0⎇⎇␈F2SECTION 1␈←
3⎇⎇␈F2␈→416⎇0⎇2⎇0⎇⎇IMPLEMENTATION OF THE STATIC STRUCTURE OF LISP␈F1␈←
4⎇⎇␈F1␈→1075⎇0⎇2⎇0⎇⎇␈F21.1  Introduction␈F1␈←
5⎇⎇␈F1The⎇material⎇in⎇the⎇previous⎇chapters⎇has⎇been⎇rather⎇abstract⎇and⎇perhaps⎇the⎇more
6⎇⎇␈F1practical-minded⎇reader⎇is⎇becoming⎇skeptical⎇of⎇this⎇whole⎇endeavor⎇␈F8 1␈F1.⎇ This⎇chapter⎇begins⎇a
7⎇⎇␈F1␈F8 1␈F1⎇"Oh,⎇ye⎇of⎇little⎇faith!"
8⎇⎇␈F1________________
9⎇⎇␈F1discussion⎇of⎇the⎇actual⎇mechanisms⎇which⎇underlie⎇a⎇typical⎇implementation⎇of⎇LISP.⎇However⎇the
10⎇⎇␈F1importance⎇of⎇the⎇techniques⎇we⎇will⎇describe⎇extends⎇far⎇beyond⎇the⎇implementation⎇of⎇this
11⎇⎇␈F1particular⎇language.⎇Most⎇of⎇the⎇ideas⎇involved⎇in⎇our⎇implementation⎇are⎇now⎇considered⎇standard
12⎇⎇␈F1system⎇programming⎇techniques⎇and⎇are⎇common⎇tools⎇in⎇language⎇design.⎇LISP⎇is⎇particularly
13⎇⎇␈F1well-suited⎇to⎇the⎇task⎇of⎇explicating⎇these⎇ideas⎇since⎇many⎇find⎇their⎇origins⎇in⎇the⎇first⎇LISP
14⎇⎇␈F1implementation.
15⎇⎇␈F1We⎇will⎇begin⎇our⎇discussion⎇of⎇implementation⎇with⎇an⎇analysis⎇of⎇storage⎇regimes⎇for
16⎇⎇␈F1S-expressions.⎇As⎇with⎇the⎇more⎇abstract⎇discussions⎇of⎇representations,⎇the⎇"concrete"⎇representation
17⎇⎇␈F1which⎇we⎇pick⎇for⎇our⎇data⎇structures⎇(S-expressions)⎇will⎇have⎇direct⎇bearing⎇on⎇the
18⎇⎇␈F1implementation⎇of⎇the⎇primitive⎇constructor⎇(␈F3cons␈F1),⎇selectors⎇(␈F3car,⎇cdr␈F1)⎇and⎇predicates⎇(␈F3atom,⎇eq␈F1)⎇of
19⎇⎇␈F1LISP.
20⎇⎇␈F1Since⎇we⎇are⎇now⎇attempting⎇to⎇become⎇less⎇mathematical⎇and⎇more⎇practical,⎇we⎇must⎇worry⎇about
21⎇⎇␈F1the⎇efficiency⎇of⎇the⎇implementation⎇␈F8 2␈F1,⎇and⎇we⎇must⎇worry⎇about⎇input/output⎇mechanisms⎇so⎇that
22⎇⎇␈F1␈F8 2␈F1⎇But⎇not⎇to⎇the⎇detriment⎇of⎇generality⎇or⎇good⎇program⎇design.
23⎇⎇␈F1the⎇language⎇may⎇communicate⎇with⎇the⎇external⎇world.
24⎇⎇␈F1The⎇present⎇chapter⎇will⎇develop⎇a⎇picture⎇of⎇this⎇␈F2static␈F1⎇structure⎇of⎇an⎇implementation,⎇or⎇perhaps
25⎇⎇␈F1to⎇be⎇more⎇graphic,⎇this⎇chapter⎇describes⎇the⎇memory⎇of⎇a⎇LISP⎇machine.⎇ The⎇next⎇chapter
26⎇⎇␈F1discusses⎇the⎇control⎇structures⎇necessary⎇to⎇properly⎇evaluate⎇expressions⎇involving⎇recursive
27⎇⎇␈F1functions.⎇The⎇description⎇of⎇the⎇␈F2dynamic␈F1⎇structure⎇of⎇LISP⎇is⎇a⎇natural⎇setting⎇in⎇which⎇to⎇discuss
28⎇⎇␈F1compilers⎇for⎇LISP.⎇For⎇example⎇a⎇complier,⎇when⎇given⎇a⎇form,⎇generates⎇machine⎇instructions,
29⎇⎇␈F1which⎇when⎇executed⎇will⎇have⎇the⎇same⎇computational⎇effect⎇as⎇the⎇evaluation⎇of⎇the⎇form⎇by⎇the
30⎇⎇␈F1interpreter.⎇The⎇code⎇generated⎇by⎇the⎇compiler⎇must⎇obey⎇all⎇of⎇the⎇control⎇structure⎇conventions
31⎇⎇␈F1imposed⎇by⎇the⎇implementation.⎇ As⎇we⎇handle⎇the⎇questions⎇of⎇compilers,⎇we⎇will⎇discuss⎇the
32⎇⎇␈F1dynamics⎇of⎇LISP.
33⎇⎇␈F1Throughout⎇these⎇discussions⎇we⎇will⎇walk⎇a⎇narrow⎇line,⎇attempting⎇to⎇remain⎇as⎇abstract⎇as
34⎇⎇␈F1␈F216415⎇  static structure␈→1265⎇222⎇1⎇0⎇⎇1.1␈F1␈←
35⎇⎇␈F1possible⎇without⎇losing⎇too⎇much⎇detail,⎇while⎇at⎇the⎇same⎇time,⎇not⎇degenerating⎇into⎇a⎇discussion
36⎇⎇␈F1of⎇coding⎇tricks.⎇Thus⎇we⎇will⎇attempt⎇to⎇describe⎇the⎇"logical"⎇structure⎇of⎇a⎇LISP⎇machine,⎇even
37⎇⎇␈F1though⎇an⎇efficient⎇implementation⎇might⎇map⎇differing⎇logical⎇structures⎇onto⎇the⎇same⎇physical
38⎇⎇␈F1structures⎇by⎇utilizing⎇machine-dependent⎇techniques.
39⎇⎇␈F1As⎇a⎇gesture⎇of⎇good⎇faith⎇we⎇will⎇now⎇resurrect⎇our⎇"box-notation"⎇for⎇S-expressions⎇(page⎇898⎇)
40⎇⎇␈F1and⎇show⎇how⎇this⎇notation⎇mirrors⎇the⎇logical⎇(and⎇usually⎇physical)⎇structure⎇of⎇LISP⎇memory,
41⎇⎇␈F1and⎇show⎇how⎇to⎇represent⎇simple⎇LISP⎇operations⎇in⎇a⎇concise⎇graphical⎇notation⎇which
42⎇⎇␈F1manipulates⎇these⎇boxes.⎇ Actual⎇hardware⎇instructions⎇usually⎇exist⎇to⎇simulate⎇these
43⎇⎇␈F1manipulations.
44⎇⎇␈F1␈→702⎇0⎇2⎇0⎇⎇␈F21.2  Representation of Symbolic expressions␈F1␈←
45⎇⎇␈F1In⎇this⎇section⎇we⎇will⎇introduce⎇notation⎇for⎇discussing⎇a⎇typical⎇implementation⎇of⎇the⎇primitive
46⎇⎇␈F1data⎇structures⎇of⎇LISP.⎇ We⎇previously⎇have⎇expressed⎇the⎇dotted⎇pair⎇␈F3(A .(B . C))␈F1⎇as:
47⎇⎇␈FG                    /\
48⎇⎇␈FG                   /  \
49⎇⎇␈FG                  /   /\
50⎇⎇␈FG                 /   /  \
51⎇⎇␈FG                ␈F3A␈FG   ␈F3B␈FG   ␈F3C␈FG
52⎇⎇␈F1or⎇occasionally⎇as:
53⎇⎇␈FB                ⊂αααπααα⊃            ⊂αααπααα⊃
54⎇⎇␈FB          ααααα→~ # ~ #αβααααααααααα→~ # ~ # ~
55⎇⎇␈FB                %αβα∀ααα$            %αβα∀αβα$
56⎇⎇␈FB                  ↓                    ↓   ↓
57⎇⎇␈FB                  ␈F3A␈FB                    ␈F3B␈FB   ␈F3C␈FB
58⎇⎇␈F1This⎇second⎇style⎇of⎇graphical⎇representation⎇has⎇a⎇direct⎇representation⎇in⎇terms⎇of⎇storage⎇layout
59⎇⎇␈F1in⎇most⎇machines.⎇ Namely⎇the⎇"box"⎇will⎇be⎇represented⎇by⎇a⎇machine⎇location⎇and⎇the⎇arrow⎇or
60⎇⎇␈F1␈F2pointer␈F1⎇will⎇be⎇represented⎇as⎇a⎇machine⎇address.⎇ For⎇example,⎇we⎇define⎇a⎇special⎇register⎇␈FBAC␈F1
61⎇⎇␈F1which⎇can⎇contain⎇representations⎇of⎇pointers.⎇Then⎇each⎇box⎇or⎇machine⎇location⎇will⎇contain⎇two
62⎇⎇␈F1pointers;⎇the⎇pointers⎇will⎇reference⎇either⎇atoms⎇(␈F3A, B, ␈F1or␈F3C␈F1)⎇or⎇will⎇point⎇at⎇other⎇machine⎇locations.
63⎇⎇␈F1Atoms⎇will⎇also⎇be⎇represented⎇by⎇machine⎇locations;⎇only⎇here⎇the⎇contents⎇of⎇such⎇a⎇location⎇must
64⎇⎇␈F1not⎇be⎇interpreted⎇as⎇a⎇pointer.⎇ To⎇help⎇keep⎇track⎇of⎇the⎇different⎇uses⎇of⎇machine⎇locations⎇we
65⎇⎇␈F1will⎇partition⎇our⎇machine's⎇memory⎇into⎇two⎇disjoint⎇spaces:⎇␈F2pointer⎇space␈F1,⎇the⎇area⎇which⎇will
66⎇⎇␈F1contain⎇pointers;⎇and⎇␈F2atom⎇space␈F1⎇which⎇will⎇contain⎇information⎇like⎇atoms⎇which⎇should⎇not⎇be
67⎇⎇␈F1interpreted⎇as⎇pointers.
68⎇⎇␈F1Thus⎇if⎇the⎇first⎇box⎇in⎇our⎇example⎇were⎇represented⎇by⎇location⎇␈FB100␈F1⎇and⎇the⎇second⎇were
69⎇⎇␈F1represented⎇by⎇location⎇␈FB405␈F1,⎇and⎇the⎇atoms⎇␈F3A␈F1,⎇␈F3B␈F1,⎇and⎇␈F3C␈F1⎇were⎇represented⎇by⎇the⎇numbers⎇␈FB40␈F1,⎇␈FB41␈F1,
70⎇⎇␈F1␈F21.2␈→705⎇33⎇1⎇0⎇⎇Representation of Symbolic expressions     16424⎇␈F1␈←
71⎇⎇␈F1and⎇␈FB42␈F1,⎇and⎇were⎇to⎇be⎇found⎇in⎇locations⎇␈FB710␈F1,⎇␈FB762␈F1,⎇and⎇␈FB711␈F1,⎇respectively,⎇then⎇the⎇following
72⎇⎇␈F1picture⎇could⎇represent⎇the⎇dotted⎇pair⎇␈F3(A .(B . C))␈F1.
73⎇⎇␈FB                        ⊂αααααααα⊃
74⎇⎇␈FB                  AC    ~    100 ~
75⎇⎇␈FB                        %αααααααα$
76⎇⎇␈FB                          ...
77⎇⎇␈FB                        ⊂αααααπααααα⊃
78⎇⎇␈FB                  100   ~ 710 ~ 405 ~
79⎇⎇␈FB                        %ααααα∀ααααα$
80⎇⎇␈FB                           ...
81⎇⎇␈FB                        ⊂αααααπααααα⊃
82⎇⎇␈FB                  405   ~ 762 ~ 711 ~
83⎇⎇␈FB                        %ααααα∀ααααα$
84⎇⎇␈FB                           ...
85⎇⎇␈FB                        ⊂ααααααααααα⊃
86⎇⎇␈FB                  710   ~      40   ~
87⎇⎇␈FB                        εαααααααααααλ
88⎇⎇␈FB                  711   ~      42   ~
89⎇⎇␈FB                        %ααααααααααα$
90⎇⎇␈FB                           ...
91⎇⎇␈FB                        ⊂ααααααααααα⊃
92⎇⎇␈FB                  762   ~       41  ~
93⎇⎇␈FB                        %ααααααααααα$
94⎇⎇␈F1This⎇representation⎇of⎇Symbolic⎇expressions⎇is⎇a⎇special⎇case⎇of⎇a⎇scheme⎇called⎇␈F2linked⎇allocation␈F1.
95⎇⎇␈F1The⎇expression⎇␈F2linked␈F1⎇refers⎇to⎇the⎇fact⎇that⎇to⎇find⎇succeeding⎇elements⎇in⎇the⎇S-expr⎇we⎇must
96⎇⎇␈F1follow⎇the⎇explicit⎇pointers.⎇The⎇particular⎇brand⎇of⎇linked⎇allocation⎇which⎇we⎇have⎇demonstrated
97⎇⎇␈F1is⎇called⎇␈F2single⎇linking␈F1⎇␈F8 3␈F1.⎇ In⎇the⎇case⎇of⎇LISP,⎇the⎇terminology⎇means⎇that⎇the⎇representation⎇of
98⎇⎇␈F1␈F8 3␈F1⎇also⎇called⎇"LISP-type⎇allocation"
99⎇⎇␈F1________________
100⎇⎇␈F1each⎇pointer⎇only⎇tells⎇us⎇how⎇to⎇find⎇succeeding⎇elements⎇in⎇the⎇structure.⎇For⎇example⎇if⎇we⎇were
101⎇⎇␈F1looking⎇at⎇location⎇␈FB405␈F1⎇the⎇representation⎇tells⎇us⎇how⎇to⎇find⎇the⎇␈F3car␈F1⎇or⎇␈F3cdr␈F1;⎇they're⎇at⎇␈FB762␈F1⎇and⎇␈FB711␈F1
102⎇⎇␈F1respectively.⎇But⎇if⎇we⎇wanted⎇to⎇find⎇the⎇␈F2predecessor␈F1⎇of⎇␈FB405␈F1⎇in⎇this⎇representation⎇it⎇would⎇require
103⎇⎇␈F1some⎇further⎇calculation.⎇ If⎇our⎇use⎇of⎇S-exprs⎇required⎇frequent⎇discovery⎇of⎇such⎇predecessors
104⎇⎇␈F1then⎇we⎇might⎇consider⎇an⎇even⎇more⎇complex⎇linked⎇representation⎇which⎇would⎇also⎇contain
105⎇⎇␈F1information⎇about⎇the⎇predecessor⎇of⎇each⎇node.⎇ We⎇will⎇examine⎇alternative⎇storage⎇techniques
106⎇⎇␈F1for⎇complex⎇data⎇structures⎇in⎇Section⎇592⎇.
107⎇⎇␈F1Data⎇structures⎇of⎇less⎇complexity⎇than⎇S-exprs⎇have⎇more⎇compact⎇representation⎇than⎇linked
108⎇⎇␈F1allocation.⎇For⎇example⎇a⎇typical⎇representation⎇of⎇a⎇vector,⎇or⎇sequence⎇of⎇fixed⎇length,⎇is⎇to⎇store
109⎇⎇␈F1the⎇elements⎇sequentially⎇in⎇memory␈F8 4␈F1.⎇ Since⎇each⎇element⎇in⎇this⎇structure⎇has⎇at⎇most⎇one
110⎇⎇␈F1␈F8 4␈F1⎇For⎇more⎇details⎇about⎇representations⎇of⎇arrays⎇and⎇vectors⎇see⎇Section⎇334⎇.
111⎇⎇␈F1successor⎇we⎇can⎇use⎇the⎇sequential⎇addresses⎇as⎇implicit⎇pointers⎇to⎇retreive⎇successive⎇elements.⎇A
112⎇⎇␈F1general⎇S-expr⎇has⎇two⎇successors;⎇thus⎇the⎇linear⎇addressing⎇scheme⎇of⎇most⎇machine⎇memories⎇is
113⎇⎇␈F1insufficient⎇as⎇it⎇stands.
114⎇⎇␈F1We⎇will⎇frequently⎇wish⎇to⎇refer⎇to⎇several⎇different⎇S-exprs⎇simultaneously;⎇for⎇example,⎇when⎇we
115⎇⎇␈F1␈F216427⎇  static structure␈→1263⎇222⎇1⎇0⎇⎇1.2␈F1␈←
116⎇⎇␈F1are⎇talking⎇about⎇the⎇implementation⎇of⎇the⎇function⎇␈F3cons␈F1⎇we⎇will⎇be⎇manipulating⎇the
117⎇⎇␈F1representations⎇of⎇two⎇S-exprs.⎇To⎇facilitate⎇such⎇discussions⎇we⎇will⎇assume⎇the⎇existence⎇of⎇a⎇set
118⎇⎇␈F1of⎇pointer⎇registers:⎇␈FBAC␈F41␈F1,⎇␈FBAC␈F42␈F1,⎇through⎇␈FBAC␈F4n␈F1.⎇ Thus,⎇using⎇the⎇above⎇example,⎇the⎇following⎇represents
119⎇⎇␈F1␈FBAC␈F41␈F1⎇pointing⎇at⎇␈F3(B . C)␈F1⎇and⎇␈FBAC␈F42␈F1⎇pointing⎇at⎇the⎇atom⎇␈F3A␈F1:
120⎇⎇␈FB           ␈F3AC␈F41␈FB                               ␈F3AC␈F42␈FB
121⎇⎇␈FB        ⊂αααααααα⊃                      ⊂αααααααα⊃
122⎇⎇␈FB        ~   405  ~                      ~   710  ~
123⎇⎇␈FB        %αααααααα$                      %αααααααα$
124⎇⎇␈F1Implicit⎇in⎇our⎇representation⎇is⎇the⎇assurance⎇that⎇we⎇can⎇differentiate⎇between⎇locations⎇in⎇atom
125⎇⎇␈F1space⎇and⎇locations⎇in⎇pointer⎇space.⎇For⎇example⎇if⎇each⎇of⎇our⎇locations⎇could⎇hold⎇at⎇most⎇six
126⎇⎇␈F1numbers⎇and⎇assume⎇we⎇will⎇store⎇numeric⎇atoms⎇as⎇the⎇corresponding⎇number.⎇Then⎇the⎇atom
127⎇⎇␈F1␈F3762711␈F1⎇would⎇be⎇stored⎇as:
128⎇⎇␈FB                        ⊂αααααααα⊃
129⎇⎇␈FB                        ~ 762711 ~
130⎇⎇␈FB                        %αααααααα$
131⎇⎇␈F1Since⎇this⎇is⎇exactly⎇the⎇contents⎇of⎇location⎇␈FB405␈F1␈F8 5␈F1⎇some⎇confusion⎇is⎇possible.⎇A⎇typical⎇trick⎇is⎇to
132⎇⎇␈F1␈F8 5␈F1⎇The⎇vertical⎇bar⎇obviously⎇doesn't⎇appear⎇in⎇the⎇machine's⎇memory.
133⎇⎇␈F1________________
134⎇⎇␈F1parition⎇memory⎇such⎇that⎇a⎇particular⎇addressing⎇space⎇corresponds⎇to⎇each⎇of⎇the⎇logical⎇spaces,
135⎇⎇␈F1atom⎇space⎇or⎇pointer⎇space.⎇In⎇our⎇example⎇we⎇might⎇assume⎇that⎇addresses⎇below⎇␈FB700␈F1⎇are
136⎇⎇␈F1locations⎇for⎇pointers,⎇while⎇addresses,⎇␈FB700␈F1⎇and⎇above⎇contain⎇atoms.⎇Thus⎇the⎇representation⎇of
137⎇⎇␈F1␈F3762711␈F1⎇would⎇appear⎇in⎇a⎇location⎇with⎇address⎇␈FB700␈F1⎇or⎇greater.
138⎇⎇␈F1We⎇still⎇aren't⎇out⎇of⎇the⎇woods⎇yet:⎇if⎇we⎇wish⎇to⎇represent⎇␈F340␈F1⎇as⎇␈FB40␈F1⎇then⎇we⎇still⎇have⎇a⎇conflict
139⎇⎇␈F1with⎇our⎇proposed⎇representation⎇of⎇the⎇atom⎇␈F3A␈F1⎇as⎇␈FB40␈F1.⎇The⎇next⎇section⎇examines⎇the⎇question⎇of
140⎇⎇␈F1what⎇is⎇a⎇reasonable⎇representation⎇for⎇literal⎇atoms␈F8 6␈F1.
141⎇⎇␈F1␈F8 6␈F1⎇or⎇non-numeric⎇atoms
142⎇⎇␈F1␈→925⎇0⎇2⎇0⎇⎇␈F21.3  Symbol tables: revisited␈F1␈←
143⎇⎇␈F1There⎇are⎇some⎇rather⎇gross⎇defects⎇in⎇our⎇symbol⎇table⎇mechanism.⎇ First,⎇we⎇have⎇had⎇to⎇resort⎇to
144⎇⎇␈F1a⎇certain⎇subterfuge⎇to⎇put⎇the⎇definitions⎇of⎇our⎇functions⎇in⎇our⎇symbol⎇table.⎇ Using⎇␈F3label␈F1
145⎇⎇␈F1(Section⎇367⎇),⎇or⎇calling⎇␈F3eval␈F1⎇with⎇an⎇initial⎇symbol⎇table,⎇only⎇defines⎇the⎇function⎇for⎇␈F2that␈F1
146⎇⎇␈F1particular⎇call⎇on⎇␈F3eval␈F1.⎇When⎇we⎇finish⎇the⎇computation,⎇the⎇definition⎇disappears.⎇ From⎇a
147⎇⎇␈F1practical⎇point⎇of⎇view⎇definitions⎇should⎇have⎇some⎇permanence.⎇ An⎇implemented⎇version⎇of
148⎇⎇␈F1LISP⎇should⎇know⎇a⎇lot⎇more⎇functions⎇than⎇the⎇five⎇primitives.⎇ It⎇should⎇have⎇a⎇reasonable⎇class
149⎇⎇␈F1of⎇arithmetic⎇functions,⎇and⎇some⎇commonly⎇used⎇Sexpr⎇functions⎇(like⎇␈F3length,⎇assoc,⎇subst,⎇equal,␈F1
150⎇⎇␈F1etc.)⎇all⎇predefined.⎇ If⎇we⎇do⎇things⎇right⎇we⎇should⎇be⎇able⎇to⎇use⎇the⎇mechanism⎇for⎇predefining
151⎇⎇␈F1functions⎇as⎇the⎇tool⎇for⎇adding⎇our⎇own⎇definitions.
152⎇⎇␈F1Second,⎇the⎇table⎇look-up⎇mechanism⎇of⎇␈F3assoc␈F1,⎇though⎇theoretically⎇sound,⎇leaves⎇something⎇to⎇be
153⎇⎇␈F1␈F21.3␈→928⎇33⎇1⎇0⎇⎇Symbol tables: revisited     16429⎇␈F1␈←
154⎇⎇␈F1desired⎇as⎇far⎇as⎇efficiency⎇is⎇concerned.⎇Since⎇we⎇do⎇wish⎇to⎇implement⎇LISP,⎇we⎇should⎇be
155⎇⎇␈F1concerned⎇with⎇efficient⎇operations.⎇We⎇will⎇see⎇that⎇an⎇efficient⎇and⎇powerful⎇symbol⎇table
156⎇⎇␈F1structure⎇can⎇be⎇described⎇quite⎇easily⎇in⎇LISP.
157⎇⎇␈F1Third,⎇we⎇have⎇already⎇seen⎇that⎇special⎇forms⎇␈F3QUOTE␈F1⎇and⎇␈F3COND␈F1⎇are⎇not⎇evaluated⎇in
158⎇⎇␈F1call-by-value⎇style.⎇Currently⎇the⎇recognizers⎇for⎇special⎇forms⎇are⎇encoded⎇in⎇␈F3eval␈F1,⎇and⎇when⎇an
159⎇⎇␈F1instance⎇of⎇such⎇a⎇form⎇is⎇seen⎇the⎇argument⎇is⎇passed⎇␈F2unevaluated␈F1⎇to⎇a⎇function⎇to⎇perform⎇the
160⎇⎇␈F1required⎇operations.⎇ It⎇would⎇be⎇nice⎇to⎇extend⎇this⎇flexibility⎇to⎇the⎇user.⎇We⎇would⎇like⎇to⎇have
161⎇⎇␈F1notation⎇for⎇adding⎇λ-definitions⎇of⎇special⎇forms⎇to⎇our⎇symbol⎇table.⎇␈F3eval␈F1⎇would⎇then⎇need⎇a⎇way
162⎇⎇␈F1of⎇distinguishing⎇a⎇λ-expression⎇defining⎇a⎇function⎇from⎇a⎇λ-expression⎇defining⎇a⎇special⎇form.
163⎇⎇␈F1Also⎇there⎇are⎇other⎇calling⎇sequences⎇which⎇are⎇interesting⎇and⎇useful⎇and⎇would⎇be⎇nice⎇to⎇have.
164⎇⎇␈F1The⎇current⎇version⎇of⎇␈F3eval␈F1⎇only⎇handles⎇function⎇definitions.⎇Thus⎇the⎇current⎇symbol⎇need⎇only
165⎇⎇␈F1store⎇the⎇λ-definition⎇and⎇does⎇not⎇need⎇explicit⎇information⎇saying⎇it⎇is⎇a⎇␈F2function␈F1⎇definition.
166⎇⎇␈F1Fourth,⎇conceptually⎇we⎇could⎇use⎇a⎇more⎇powerful⎇mechanism.⎇ Consider⎇␈F3car[car]␈F1⎇as⎇an⎇expression
167⎇⎇␈F1to⎇be⎇evaluated.⎇Perhaps⎇it⎇is⎇best⎇just⎇to⎇say⎇the⎇expression⎇is⎇ill-formed,⎇but⎇if⎇you⎇knew⎇that⎇␈F3car␈F1
168⎇⎇␈F1also⎇was⎇currently⎇being⎇used⎇as⎇a⎇simple⎇variable⎇besides⎇being⎇a⎇function,⎇then⎇your⎇intuition⎇says
169⎇⎇␈F1the⎇first⎇occurrence⎇of⎇␈F3car␈F1⎇is⎇a⎇function⎇name⎇and⎇the⎇second⎇occurrence⎇is⎇the⎇simple⎇variable
170⎇⎇␈F1name;⎇and⎇if⎇the⎇current⎇value⎇of⎇␈F3car␈F1⎇was⎇say,⎇␈F3(A⎇B)␈F1⎇then⎇␈F3car[car]␈F1⎇should⎇evaluate⎇to⎇␈F3A␈F1.⎇ That⎇is,
171⎇⎇␈F1context⎇tells⎇us⎇which⎇occurrence⎇of⎇␈F3car␈F1⎇is⎇a⎇function⎇and⎇which⎇is⎇a⎇simple⎇variable⎇␈F8 7␈F1.⎇ The
172⎇⎇␈F1␈F8 7␈F1⎇just⎇as⎇an⎇evaluator⎇for⎇␈F3prog␈F1⎇can⎇tell⎇a⎇reference⎇to⎇the⎇label⎇␈F3x␈F1⎇from⎇the⎇␈F3prog␈F1-variable⎇␈F3x␈F1⎇in
173⎇⎇␈F1________________
174⎇⎇␈F1␈F3 ... prog[[x;y] .. x f[..] ... g[x .. ] ... go[x].␈F1⎇See⎇page⎇535⎇.
175⎇⎇␈F1current⎇␈F3eval␈F1⎇␈F2will␈F1⎇operate⎇correctly⎇on⎇this⎇example⎇since⎇a⎇recognizer⎇for⎇the⎇function⎇␈F3car␈F1⎇is
176⎇⎇␈F1explicitly⎇encoded⎇in⎇␈F3apply␈F1.⎇ ␈F8 8␈F1.⎇ However,⎇in⎇general⎇our⎇current⎇symbol⎇table⎇mechanism⎇is⎇not
177⎇⎇␈F1␈F8 8␈F1⎇For⎇the⎇same⎇reason,⎇the⎇LISP⎇obscenity⎇␈F3λ[[lambda]⎇...⎇]␈F1⎇will⎇work.⎇Notice⎇its⎇sexpr⎇representation
178⎇⎇␈F1is⎇␈F3(LAMBDA (LAMBDA) ⎇... )␈F1
179⎇⎇␈F1sufficient⎇for⎇this⎇interpretation.⎇Forced⎇to⎇use⎇␈F3assoc␈F1,⎇we⎇would⎇only⎇find⎇the⎇␈F2first␈F1⎇binding⎇of⎇a
180⎇⎇␈F1variable.⎇It⎇will⎇either⎇be⎇a⎇λ-expression⎇(function)⎇or⎇a⎇simple⎇value.⎇Context⎇will⎇determine⎇how
181⎇⎇␈F1␈F3eval␈F1⎇will⎇interpret⎇what⎇is⎇found.⎇ Clearly⎇what⎇is⎇needed⎇is⎇the⎇ability⎇to⎇associate⎇more⎇than⎇one
182⎇⎇␈F1property⎇with⎇an⎇atom.⎇In⎇the⎇above⎇example⎇␈F3car␈F1⎇has⎇(at⎇least)⎇two⎇␈F2properties␈F1⎇or⎇␈F2attributes␈F1.⎇ It⎇has
183⎇⎇␈F1a⎇function⎇value⎇and⎇it⎇has⎇a⎇simple⎇value.⎇Since⎇␈F3car␈F1⎇is⎇a⎇primitive⎇function,⎇its⎇function⎇value⎇is
184⎇⎇␈F1the⎇location⎇of⎇the⎇machine⎇code⎇to⎇carry⎇out⎇the⎇␈F3car␈F1⎇function;⎇the⎇simple⎇value⎇is⎇the⎇sexpr
185⎇⎇␈F1currently⎇bound⎇to⎇the⎇variable,⎇␈F3car␈F1.
186⎇⎇␈F1These⎇last⎇three⎇desires,⎇for⎇permanence,⎇generality,⎇and⎇for⎇multiple⎇properties,⎇can⎇be⎇handled⎇by
187⎇⎇␈F1the⎇same⎇mechanism.⎇Clearly⎇we⎇could⎇continue⎇using⎇an⎇␈F3assoc␈F1-like⎇table,⎇though⎇more⎇complicated,
188⎇⎇␈F1storing⎇information⎇about⎇what⎇kind⎇of⎇value⎇each⎇dotted⎇pair⎇is.⎇However⎇our⎇desire⎇for⎇efficiency
189⎇⎇␈F1would⎇certainly⎇not⎇be⎇satisfied.⎇Rather,⎇we⎇will⎇design⎇a⎇new⎇symbol⎇table⎇which⎇can⎇store⎇with
190⎇⎇␈F1each⎇atom⎇sequences⎇of⎇values⎇and⎇their⎇types.⎇This⎇gives⎇us⎇multiple⎇properties.⎇ We⎇will⎇make⎇the
191⎇⎇␈F1table⎇␈F2global␈F1⎇to⎇␈F3eval␈F1⎇and⎇␈F3apply␈F1;⎇these⎇functions⎇will⎇now⎇implicitly⎇refer⎇to⎇that⎇table⎇and⎇thus⎇need
192⎇⎇␈F1not⎇have⎇an⎇explicit⎇symbol-table⎇argument.⎇This⎇gives⎇us⎇permanence.⎇We⎇will⎇designate⎇an
193⎇⎇␈F1indicator⎇for⎇function⎇definition⎇and⎇an⎇indicator⎇for⎇special⎇form⎇definition⎇and⎇expand⎇␈F3eval␈F1⎇and
194⎇⎇␈F1␈F3apply␈F1⎇to⎇recognize⎇these⎇indicators.⎇ This⎇gives⎇us⎇generality.
195⎇⎇␈F1Most⎇implementations⎇of⎇LISP⎇allow⎇this⎇association⎇of⎇arbitrary⎇sequences⎇of⎇␈F6attribute-value␈F1⎇pairs
196⎇⎇␈F1␈F216430⎇  static structure␈→1263⎇222⎇1⎇0⎇⎇1.3␈F1␈←
197⎇⎇␈F1with⎇an⎇atom.⎇ It⎇is⎇a⎇very⎇good⎇idea.⎇ How⎇can⎇we⎇associate⎇an⎇arbitrary⎇collection⎇of⎇objects⎇with
198⎇⎇␈F1something?⎇ With⎇each⎇atom⎇we⎇will⎇associate⎇a⎇list⎇called⎇the⎇␈F6property-list␈F1⎇or⎇p␈F6-list.␈F1⎇But⎇atoms
199⎇⎇␈F1can't⎇be⎇represented⎇as⎇just⎇any⎇other⎇list.⎇ Among⎇other⎇things,⎇we⎇must⎇be⎇able⎇to⎇recognize⎇the
200⎇⎇␈F1occurrence⎇of⎇atoms⎇so⎇that⎇we⎇can⎇implement⎇the⎇predicate,⎇␈F3atom␈F1.⎇ So⎇atoms⎇are⎇special⎇lists:⎇the⎇␈F3car␈F1
201⎇⎇␈F1(or⎇first⎇element)⎇of⎇the⎇representation⎇of⎇each⎇atom⎇is⎇an⎇indicator⎇used⎇exclusively⎇for⎇the
202⎇⎇␈F1beginning⎇of⎇atoms.⎇We⎇will⎇use⎇␈FB⊗␈F1⎇to⎇designate⎇the⎇beginning⎇of⎇an⎇atom.⎇ The⎇␈F3cdr␈F1⎇of⎇the
203⎇⎇␈F1representation⎇of⎇the⎇atom⎇is⎇the⎇property⎇list.⎇The⎇elements⎇of⎇the⎇p-list⎇are⎇associated⎇in⎇pairs.
204⎇⎇␈F1The⎇first⎇element⎇is⎇the⎇attribute⎇(or⎇property⎇or⎇indicator);⎇the⎇next⎇element⎇is⎇the⎇value.⎇ For
205⎇⎇␈F1example,⎇here⎇is⎇part⎇of⎇the⎇atom-structure⎇for⎇␈F3car␈F1⎇assuming⎇␈F3car␈F1⎇is⎇also⎇being⎇used⎇as⎇a⎇simple
206⎇⎇␈F1variable⎇and⎇has⎇current⎇value,⎇␈F3(A⎇B)␈F1:
207⎇⎇␈FB⊂ααααπαααα⊃   ⊂ααααααπαααα⊃ ⊂αααπααα⊃  ⊂αααααααπααα⊃ ⊂αααααπααα⊃
208⎇⎇␈FB~ ⊗  ~  #αβαα→~ SUBR ~  #αβ→~ # ~ #αβα→~ VALUE ~ #αβ→~  #  ~     ...
209⎇⎇␈FB%αααα∀αααα$   %αααααα∀αααα$ %αβα∀ααα$  %ααααααα∀ααα$ %ααβαα∀ααα$
210⎇⎇␈FB                              ~                         ~
211⎇⎇␈FB                              ~                         ~
212⎇⎇␈FB        to machine code ←ααααα$         ⊂ααααααααααααααα$
213⎇⎇␈FB        for ␈F3car␈FB                     ~
214⎇⎇␈FB                                        ↓
215⎇⎇␈FB                                ⊂αααααπαααα⊃
216⎇⎇␈FB                                ~ NIL ~ #  ~
217⎇⎇␈FB                                %ααααα∀αβαα$
218⎇⎇␈FB                                        ~
219⎇⎇␈FB                                        ~
220⎇⎇␈FB                                        ↓
221⎇⎇␈FB                                        ⊂αααααπααααα⊃  ⊂αααααπααααα⊃
222⎇⎇␈FB                                        ~  A  ~  #ααβα→~  B  ~ NIL ~
223⎇⎇␈FB                                        %ααααα∀ααααα$  %ααααα∀ααααα$
224⎇⎇␈F1␈→813⎇0⎇2⎇0⎇⎇␈F2Part⎇of⎇the⎇atom-structure⎇for⎇␈F3CAR␈F1.⎇␈←
225⎇⎇␈F1The⎇indicator,⎇␈F3SUBR␈F1,⎇tells⎇us⎇that⎇␈F3car␈F1⎇is⎇a⎇machine⎇language⎇function.⎇ The⎇indicator,⎇␈F3VALUE␈F1,⎇tells
226⎇⎇␈F1us⎇that⎇␈F3car␈F1⎇is⎇also⎇being⎇used⎇as⎇a⎇simple⎇variable.⎇ The⎇reason⎇for⎇not⎇pointing⎇directly⎇at⎇␈F3(A⎇B)␈F1⎇is
227⎇⎇␈F1described⎇in⎇Section⎇776⎇.
228⎇⎇␈F1It⎇should⎇now⎇be⎇clear⎇how⎇to⎇program⎇the⎇primitive⎇predicate,⎇␈F3atom␈F1:⎇"is⎇␈F3car␈F1⎇of⎇the⎇argument⎇to
229⎇⎇␈F1␈F3atom␈F1⎇the⎇special⎇atom-indicator?"⎇If⎇it⎇is⎇then⎇␈F3atom␈F1⎇gives⎇value⎇␈F3T␈F1,⎇otherwise⎇␈F3atom␈F1⎇gives⎇value⎇␈F3NIL␈F1.
230⎇⎇␈F1How⎇about⎇the⎇representation⎇of⎇non-primitive⎇functions?⎇ Non-primitive⎇functions⎇are⎇defined
231⎇⎇␈F1using⎇λ-expressions.⎇ What⎇we⎇do⎇is⎇define⎇a⎇new⎇indicator,⎇␈F3EXPR␈F1,⎇which⎇tells⎇the⎇evaluator⎇that
232⎇⎇␈F1the⎇function⎇is⎇a⎇λ-expression.⎇ For⎇example,⎇here⎇is⎇part⎇of⎇the⎇atom-structure⎇for⎇␈F3FACT␈F1,⎇the
233⎇⎇␈F1Sexpr⎇form⎇of⎇the⎇factorial⎇function.